1. Field of the Invention
The present invention relates to a circuit and method for modulo address generation having reduced address generation delay and which requires less area to implement on an integrated circuit chip.
2. Description of the Prior Art
Generally, modulo addressing is used in digital signal processors (DSPs) to efficiently perform a DSP algorithm, such as a digital filter.
Modulo addressing is, in essence, a circular addressing method. The simplest type of modulo addressing returns to a base address (B) when reaching a predetermined maximum address (M) by incrementing a current address (A) by a predetermined address increment (I). The same data region is therefor repeatedly accessed. Modulo addressing can thus be implemented in a DSP algorithm to repeatedly access data that is located in a specific region, such as filter coefficient data, with high speed and a low level of address generation overhead. The address increment I can be either positive, for incrementing the address A, or negative, to decrement the address A.
In more general terms, given that a predetermined data region is defined by the maximum address M and the minimum address B, the modulo algorithm for the next address NEXT.sub.-- A can be expressed as described below.
First, when I.gtoreq.0 and A+I.ltoreq.M, then the next address NEXT.sub.-- A is expressed by NEXT.sub.-- A=A+I. Conversely, if I.gtoreq.0 and A+I&gt;M, then the next address NEXT.sub.-- A is expressed as follows: EQU NEXT.sub.-- A=A+I-(M-B+1) (1)
where M.gtoreq.A.gtoreq.B and I&lt;M-B+1.
Similarly, when I&lt;0 and A+I.gtoreq.B, then the next address NEXT.sub.-- A is expressed as NEXT.sub.-- A=A+I. However, when I&lt;0 and A+I&lt;B, then the next address NEXT.sub.-- A is expressed as follows: EQU NEXT.sub.-- A=A+I+(M-B+1) (2)
where M.gtoreq.A.gtoreq.B and .vertline.I.vertline.&lt;M-B+1.
However, the implementation of equations (1) and (2) above typically requires a circuit having multiple stage adders connected in series. This has the disadvantage that the modulo address generation function may become a critical path in a high speed digital signal processor due to the delay introduced by the sequentially operating multistage adders. Circuits have been constructed, such as the module addressing circuit 100 shown in FIG. 1, that use high speed adders instead of multiple stage adders in order to avoid the delay introduced by multistage adders.
Modulo addressing circuit 100 consists of a first adder 11 which adds the current address A and the address increment I and outputs a resulting sum signal a. Two multiplexors (MUXs) 12 and 13 are included for selecting and outputting either the maximum address M or the minimum address B according to the sign bit, sign(I), of the address increment I. An inverter INV inverts the output from the first MUX 12 and inputs the resulting signal b to a second adder 14 which adds the output signal a of the first adder, the output signal b of the inverter and sign(I) to produce an output signal d. A third adder 15 adds the output signal d from the second adder, the output signal c from the second MUX 13 and sign(I) to produce an output signal e. XNOR gate 16 performs an exclusive NOR operation on sign(I) and the sign bit of the output signal d from adder 14, sign(d), to control the selection in MUX 17 of either the output signal a from the first adder or the output signal e from the third adder.
To understand the function of modulo addressing circuit 100, note that when I.gtoreq.0 and A+I&gt;M, then equation (1) above can be rewritten as follows: ##EQU1##
In equation (3), inv(M) designates a one's complement of M and -M=inv(M)+1, under a two's complement representation. The relation of A+I&gt;M can therefore be expressed as A+I+inv(M).gtoreq.0. Note also that sign(I)=0 for the inputs to adders 14 and 15.
In a similar manner, when I&lt;0 and A+I&lt;B, equation (2) above can be expressed as follows: EQU NEXT.sub.-- A=A+I+(M-B+1); EQU =A+I+M+(inv(B)+1)+1 (4).
In equation (4), inv(B) designates a one's complement of B, and the equation A+I&lt;B can be expressed as A+I+inv(B)&lt;0.
The algorithm implemented by modulo addressing circuit 100 can then be expressed as follows: ##EQU2##
Modulo addressing circuit 100 can be implemented as described above using only three high speed adders and some additional logic circuitry. However, the drawback of the solution illustrated by modulo addressing circuit 100 is the increased chip area required to construct the three high speed adders 11, 14 and 15.